package algorithm.tree;

import algorithm.model.TreeNode;

/**
 * leetcode
 * 437. Path Sum III
 *
 * https://leetcode.com/problems/path-sum-iii/
 * Easy
 * Topic: Tree
 *
 * 给一个节点有值的二叉树, 和一个数字sum。(节点的值和数字是整数，可以为正和负)
 * 找出路径节点值的和恰好等于sum，的所有路径个数。
 * 注意：路径一定非得从根节点开始和叶节点结束。只要求顺序从上到下即可。
 *
 * Created by yzy on 2020-04-10 15:33
 */
public class PathSumIII {

    public static void main(String[] args) {
        TreeNode node = TreeNode.getTreeNode(new Integer[]{10,5,-3,3,2,null,11,3,-2,null,1});   // sum=8, result=3
        System.out.println(pathSum(node, 8));

        TreeNode node1 = TreeNode.getTreeNode(new Integer[]{1,null,2,null,3,null,4,null,5});    // sum=3, result=2
        System.out.println(node1);
        System.out.println(pathSum(node1,3));

    }

    /**
     * 思路：
     * 深度优先遍历 + 递推公式
     *
     * 假设：
     * path[curr] 代表从 curr 节点开始，往下查找符合sum的路径数。
     * sum[curr] 代表 从curr 节点开始，该子树所有符合的路径数
     * 那么，得出递推公式：
     * sum[curr] = path[curr] + sum[curr.left] + sum[curr.right]
     *
     * RunTime: 19ms 59.68%
     * Memory: 39MB 90.19%
     * @param root
     * @param sum
     * @return
     */
    public static int pathSum(TreeNode root, int sum) {
        if(root==null) return 0;
        return findPath(root,sum) + pathSum(root.left, sum) + pathSum(root.right, sum);
    }

    /**
     * @param node
     * @param curSum
     * @return
     */
    private static int findPath(TreeNode node, int curSum){
        if(node==null) return 0;
        int nextSum = curSum - node.val;
        int currPathNum = nextSum==0 ? 1 : 0;
        return currPathNum +
                findPath(node.left,nextSum) + findPath(node.right,nextSum);
    }



}
